package leetcode.day_2020_11_16_11_22;

import java.util.*;

public class L_15 {
    public static void main(String[] args) {
         int[] arr = {-1,0,1,2,-1,-4,-2,-3,3,0,4};
//        int[] arr = {-1, 0, 1, 2, -1, -4};
        Arrays.sort(arr);
//        for(int i=0; i<arr.length; i++)
//            System.out.println(arr[i]);
        System.out.println(threeSum2(arr));
    }

    /**
     * 此方法超时
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        HashSet<List> set = new HashSet<>();

        for(int i=0; i<nums.length; i++) {
            for(int j=i+1; j<nums.length; j++) {
                for(int k=j+1; k<nums.length; k++) {
                    if(nums[i]+nums[j]+nums[k] == 0){
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[k]);
//                        Collections.sort(list);
                        set.add(list);
                    }
                }
            }
        }
        Iterator<List> iter = set.iterator();
        for(int i=0; i<set.size()&&iter.hasNext(); i++){
            lists.add(iter.next());
        }
        return lists;
    }

    /**
     * 二分查找法
     */
    public static List<List<Integer>> threeSum2(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> lists = new ArrayList<>();
        if(nums.length < 3)
            return lists;
        HashSet<List> set = new HashSet<>();
        for(int index=4; index<nums.length; index++) {
            int left = 0, right = nums.length-1;
            while(left < right) {
                if(left == index) left++;
                if(right == index) right--;
                if(nums[index] + nums[left] + nums[right] == 0){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[index]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    Collections.sort(list);
                    set.add(list);
                    break;
                } else if(nums[index] + nums[left] + nums[right] < 0){
                    left++;
                }else {
                    right--;
                }
            }
        }
        Iterator<List> iter = set.iterator();
        for(int i=0; i<set.size()&&iter.hasNext(); i++){
            lists.add(iter.next());
        }
        return lists;
    }
}
